home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / graph_alg / _components.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  1.8 KB  |  92 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _components.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. /*******************************************************************************
  17. *                                                                              *
  18. *  COMPONENTS  (connected components)                                          *
  19. *                                                                              *
  20. *******************************************************************************/
  21.  
  22.  
  23. #include <LEDA/graph_alg.h>
  24.  
  25. #include <LEDA/node_partition.h>
  26.  
  27. static int count;
  28.  
  29. static void dfs(node v, node_array<int>& compnum)
  30. { 
  31.   node_stack  S;
  32.  
  33.   S.push(v);
  34.   compnum[v] = count;
  35.  
  36.   while (!S.empty())
  37.    { v = S.pop(); 
  38.      node w;
  39.      forall_adj_nodes(w,v) 
  40.         if (compnum[w] == -1)
  41.         { compnum[w] = count;
  42.           S.push(w);
  43.          }
  44.     }
  45.  
  46. } 
  47.  
  48. int COMPONENTS(const ugraph& G, node_array<int>& compnum)
  49. { // computes connected components of undirected graph G
  50.   // compnum[v] = i  iff v in component i
  51.   // number of components is returned
  52.  
  53.   node v;
  54.  
  55.   forall_nodes(v,G) compnum[v] = -1;
  56.  
  57.   count = 0;
  58.  
  59.   forall_nodes(v,G) 
  60.     if (compnum[v] == -1) 
  61.     { dfs(v,compnum);
  62.       count++; 
  63.      }
  64.  
  65.   return count;
  66. }
  67.  
  68.  
  69.  
  70. int COMPONENTS1(const ugraph& G, node_array<int>& compnum)
  71. { 
  72.  
  73.   node_partition P(G);
  74.   edge e;
  75.   node v;
  76.  
  77.   forall_nodes(v,G) compnum[v] = -1;
  78.  
  79.   forall_edges(e,G) P.union_blocks(source(e),target(e));
  80.  
  81.   int count = 0;
  82.   forall_nodes(v,G) 
  83.    { node w = P.find(v);
  84.      if (compnum[w]==-1) compnum[w] = count++;
  85.      compnum[v] = compnum[w];
  86.     }
  87.  
  88.   return count;
  89. }
  90.  
  91.  
  92.